In the latter half of the twentieth century, there began a phenomenon known as the information revolution. While the information revolution is a historical development broader in scope than any one event or machine, no single device has come to represent the information revolution more than the digital electronic computer. The development of computer systems has surely been a revolution. Each year, computer systems grow faster, store more data, and provide more applications to their users.
A modern computer system typically comprises hardware in the form of one or more central processing units (CPU) for processing instructions, memory for storing instructions and other data, and other supporting hardware necessary to transfer information, communicate with the external world, and so forth. From the standpoint of the computer's hardware, most systems operate in fundamentally the same manner. Processors are capable of performing a limited set of very simple operations, such as arithmetic, logical comparisons, and movement of data from one location to another. But each operation is performed very quickly. Programs which direct a computer to perform massive numbers of these simple operations give the illusion that the computer is doing something sophisticated. What is perceived by the user as a new or improved capability of a computer system is made possible by performing essentially the same set of very simple operations, but doing it much faster. Therefore continuing improvements to computer systems require that these systems be made ever faster.
The overall speed at which a computer system performs day-to-day tasks (also called “throughput”) can be increased by making various improvements to the computer's hardware design, which in one way or another increase the average number of simple operations performed per unit of time. The overall speed of the system can also be increased by making algorithmic improvements to the system design, and particularly, to the design of software executing on the system. Unlike most hardware improvements, many algorithmic improvements to software increase the throughput not by increasing the average number of operations executed per unit time, but by reducing the total number of operations which must be executed to perform a given task.
Complex systems may be used to support a variety of applications, but one common use is the maintenance of large databases, from which information may be obtained. Large databases usually support some form of database query for obtaining information which is extracted from selected database fields and records. Such queries can consume significant system resources, particularly processor resources, and the speed at which queries are performed can have a substantial influence on the overall system throughput.
Conceptually, a database may be viewed as one or more tables of information, each table having a large number of entries (analogous to row of a table), each entry having multiple respective data fields (analogous to columns of the table). The function of a database query is to find all rows, for which the data in the columns of the row matches some set of parameters defined by the query. A query may be as simple as matching a single column field to a specified value, but is often far more complex, involving multiple tables, multiple field values and multiple logical conditions.
Execution of a query involves retrieving and examining records in the database according to some strategy. For any given logical query, not all query execution strategies are equal. Various factors may affect the choice of optimum query execution strategy. For example, where a logical AND (or logical OR) of multiple conditions is specified, the sequential order in which the conditions are evaluated can make a significant difference in the time required to execute the query. The sequential order of evaluation is significant because the first evaluated condition is evaluated with respect to all the records in a database table, but a later evaluated condition need only be evaluated with respect to the subset of records for which the first condition was true. Similarly, for a query involving multiple conditions conjoined by a logical OR, a later evaluated condition need only be evaluated with respect to the subset of records for which an earlier condition was false. Therefore, as a general rule, it is desirable to evaluate those conditions which are most selective (i.e., eliminate the largest number of records from consideration) first, and to evaluate conditions which are less selective later. Other factors, such as the availability of database indexes or the relative difficulty of evaluating various conditions, may also affect the choice of optimum execution strategy.
To support database queries, large databases typically include a query engine and/or query optimizer, which executes the queries according to some automatically determined query execution strategy, using the known characteristics of the database and other factors. For the reasons explained above, in order to determine an optimum execution strategy, it is desirable to know in advance the number of records selected by each condition. Unfortunately, this is generally impossible to determine precisely in advance, without actually evaluating the conditions (i.e., without performing the query). There are, however, certain techniques whereby a query engine or optimizer may estimate the number of responsive records without actually performing the query.
Large databases typically include various auxiliary data structures to support query execution, which may be used to estimate the number of responsive records. One such structure is an index. An index is a sorting of the records in one of the database tables according to the value(s) of a corresponding field or fields. For example, if the database table contains records about people, one of the fields may contain a birthdate and a corresponding index contains a sorting of the records by birthdate. If a query requests the records of all persons born before a particular date, the sorted index may be used to find the responsive records, without the need to examine each and every record to determine whether there is a match. Another index may contain a sorting of the records by last name. In a similar index or another index, it may be useful to sort on multiple fields, e.g., by last name and first name (the first name being used as a secondary sorting, only if the last names of multiple records are identical). A well-designed database typically contains a respective index for each field having an ordered value which is likely to be used in queries.
Another such auxiliary data structure is a frequent value list. A frequent value list contains a listing, for a particular database field in a particular table, of discrete values of the field and corresponding frequency of occurrence. A third such auxiliary data structure is a histogram, which records the values of an ordered database field corresponding to ordered subsets having approximately equal numbers of entries. A frequent value list and a histogram typically contain approximate values, derived using any of various conventional techniques.
Conventional auxiliary database structures and techniques provide some assistance in estimating numbers of responsive records to various query conditions, but they are far from ideal. One type of query condition which is particularly difficult to evaluate using conventional techniques is a join condition requiring a comparison of values from more than one table in the database. Conventional auxiliary data structures generally characterize a single table, and are optimally used to estimate responses to queries involving data in one table. When values from multiple tables are joined, the size of the response set can be unpredictable as a result of data skew, i.e., the fact that values in a particular field are not evenly distributed. In other words, where a database table contains many records having the same value for one of its fields, and a query condition involves a join of this field with a second field of a another table, it is difficult to predict how many records will match the query condition. If the responsive records from the second table do not match the frequently occurring value in the first table, there might be very few records meeting the join condition; if, on the other hand, even a small number of records from the second table matches the frequently occurring value in the first table, the result set could be very large.
The unpredictability of database join queries has long been recognized in the art, and various conventional techniques exist for estimating result set size for a join condition. For example, it is known to apply the join query condition to a small randomly sampled portion of the database and extrapolate a result set size from the result set of the sample. Unfortunately, these and other conventional techniques do not always produce accurate predictions, particularly where substantial data skew exists.
In order to improve the optimization of database queries, it would be desirable to provide more accurate predictions of the number of records responsive to a database query condition involving joins, and in particular, responsive to a join query condition where a joined value exhibits substantial data skew.